package com.tgy.leetcode.binarysearch;

import lombok.val;

/**
 * @Author: tgy
 * @Date: 12/18/20 1:57 PM
 */
public class BinarySearch {

    /**
     * 1）二分查找元素value的下标，如无 return -1
     * @param nums
     * @param val
     * @return
     */
    public static int searchEqualValue(int[] nums,int val) {

        if (nums == null || nums.length == 0) {

            return -1;
        }

        int left = 0, right = nums.length, mid;

        while (left < right) {

            mid = (left + right) >> 1;

            if ( val < nums[mid]) {

                right = mid;
            }else if (val > nums[mid]) {

                left = mid + 1;
            }else {

                return mid;
            }
        }

        return -1;
    }

    /**
     * 二分查找返回value(可能有重复)第一次出现的下标，如无return -1
     * @param nums
     * @param val
     * @return
     */
    public static int searchFirstEqualValue(int[] nums,int val) {

        if (nums == null || nums.length == 0) {

            return -1;
        }

        int left = 0, right = nums.length,mid;

        while (left + 1 < right) {

            mid = (left + right) >> 1;

            if (val <= nums[mid]) {

                right = mid;
            }else {

                left = mid;
            }
        }

        return (right < nums.length &&  nums[right] == val) ? right:-1;
    }

    /**
     * 二分查找返回value(可能有重复)最后一次出现的下标，如无return -1
     * @param nums 1,3,4,4,4,4,4,5,6,7,9,18
     * @param val
     * @return
     */
    public static int searchLastEqualValue(int[] nums, int val) {

        if (nums == null || nums.length == 0) {

            return -1;
        }

        int left = 0, right = nums.length, mid;

        /**
         * 这里 使用 left+1 < right 是为了防止最后剩下两个元素，最后计算的mid始终与left相等，从而引起死循环
         *
         */
        while (left + 1 < right) {

            mid = (left + right) >> 1;

            if (val >= nums[mid]) {

                left = mid;
            }else if (val < nums[mid]){

                // right 指向的元素始终大于 val
                right = mid;
            }
        }

        return nums[left] == val?left:-1;
    }

    /**
     * 二分查找返回刚好小于value的元素下标，如无return -1
     * @param nums
     * @param val
     * @return
     */
    public static int searchLastLessThanValue(int[] nums, int val) {

        if (nums == null || nums.length == 0) {

            return -1;
        }

        /**
         * 处理极端情况
         */
        if (nums[0] >= val) {

            return -1;
        }

        if (nums[nums.length - 1] < val) {

            return nums.length - 1;
        }


        /**
         * right 要么指向数组长度，要么就是指向大于等于value的位置
         */
        int left = 0, right = nums.length, mid;

        while (left + 1 < right) {

            mid = (left + right) >> 1;

            if (val <= nums[mid]) {

                right = mid;
            }else {

                left = mid;
            }
        }

        return left;
    }

    /**
     * 二分查找返回刚好大于value的元素下标，如无return -1
     * @param nums
     * @param val
     * @return
     */
    public static int searchFirstGreaterThanValue(int[] nums, int val) {

        if (nums == null || nums.length == 0) {

            return -1;
        }

        /**
         * 处理极端情况
         */
        if (nums[0] > val) {

            return 0;
        }

        if (nums[nums.length - 1] < val) {

            return -1;
        }

        int left = 0, right = nums.length, mid;

        while (left + 1 < right) {

            mid = (left + right) >> 1;

            if (val < nums[mid]) {

                right = mid;
            }else {

                left = mid;
            }
        }

        return right;
    }
}
